#include <iostream>
#include <stack>
#include <queue>
#include <unordered_map>
#include <list>
#include <string>
#include <vector>
using namespace std;

// 1. 使用栈检查括号匹配
bool isValidParentheses(const string& s) {
    cout << "=== 括号匹配检查 ===" << endl;
    cout << "检查字符串: \"" << s << "\"" << endl;
    
    stack<char> st;
    
    for(char c : s) {
        if(c == '(' || c == '[' || c == '{') {
            st.push(c);
            cout << "入栈: " << c << endl;
        } else if(c == ')' || c == ']' || c == '}') {
            if(st.empty()) {
                cout << "栈为空，无法匹配 " << c << endl;
                return false;
            }
            
            char top = st.top();
            cout << "栈顶: " << top << ", 当前字符: " << c << endl;
            
            if((c == ')' && top == '(') ||
               (c == ']' && top == '[') ||
               (c == '}' && top == '{')) {
                st.pop();
                cout << "匹配成功，出栈: " << top << endl;
            } else {
                cout << "匹配失败" << endl;
                return false;
            }
        }
    }
    
    bool result = st.empty();
    cout << "最终结果: " << (result ? "匹配成功" : "匹配失败") << endl;
    return result;
}

// 2. 使用队列和哈希表实现LRU缓存
class LRUCache {
private:
    int capacity;
    unordered_map<int, list<pair<int, int>>::iterator> cacheMap;
    list<pair<int, int>> cacheList;

public:
    LRUCache(int cap) : capacity(cap) {
        cout << "创建LRU缓存，容量: " << capacity << endl;
    }
    
    int get(int key) {
        auto it = cacheMap.find(key);
        if(it == cacheMap.end()) {
            cout << "获取键 " << key << ": 未找到 (-1)" << endl;
            return -1;
        }
        
        // 移动到链表头部（最近使用）
        cacheList.splice(cacheList.begin(), cacheList, it->second);
        cout << "获取键 " << key << ": " << it->second->second << " (移动到头部)" << endl;
        return it->second->second;
    }
    
    void put(int key, int value) {
        auto it = cacheMap.find(key);
        if(it != cacheMap.end()) {
            // 键已存在，更新值并移动到头部
            it->second->second = value;
            cacheList.splice(cacheList.begin(), cacheList, it->second);
            cout << "更新键 " << key << " = " << value << " (移动到头部)" << endl;
            return;
        }
        
        if(cacheMap.size() >= capacity) {
            // 删除最近最少使用的元素（链表尾部）
            int lruKey = cacheList.back().first;
            cacheMap.erase(lruKey);
            cacheList.pop_back();
            cout << "缓存已满，删除LRU键: " << lruKey << endl;
        }
        
        // 插入新元素到头部
        cacheList.emplace_front(key, value);
        cacheMap[key] = cacheList.begin();
        cout << "插入新键 " << key << " = " << value << " (在头部)" << endl;
    }
    
    void display() {
        cout << "当前缓存内容 (从最近到最久): ";
        for(const auto& pair : cacheList) {
            cout << "(" << pair.first << ":" << pair.second << ") ";
        }
        cout << endl;
    }
};

// 3. 使用栈实现表达式求值（中缀转后缀）
class ExpressionEvaluator {
private:
    // 获取操作符优先级
    int getPrecedence(char op) {
        if(op == '+' || op == '-') return 1;
        if(op == '*' || op == '/') return 2;
        return 0;
    }
    
    // 判断是否为操作符
    bool isOperator(char c) {
        return c == '+' || c == '-' || c == '*' || c == '/';
    }
    
    // 判断是否为数字
    bool isDigit(char c) {
        return c >= '0' && c <= '9';
    }

public:
    // 中缀转后缀表达式
    string infixToPostfix(const string& infix) {
        cout << "=== 中缀转后缀表达式 ===" << endl;
        cout << "中缀表达式: " << infix << endl;
        
        stack<char> operators;
        string postfix = "";
        
        for(char c : infix) {
            if(isDigit(c)) {
                postfix += c;
                cout << "数字 " << c << " 直接输出" << endl;
            } else if(c == '(') {
                operators.push(c);
                cout << "左括号 ( 入栈" << endl;
            } else if(c == ')') {
                while(!operators.empty() && operators.top() != '(') {
                    postfix += operators.top();
                    cout << "右括号 ) 遇到，出栈操作符: " << operators.top() << endl;
                    operators.pop();
                }
                operators.pop(); // 移除左括号
                cout << "移除左括号 (" << endl;
            } else if(isOperator(c)) {
                while(!operators.empty() && 
                      operators.top() != '(' && 
                      getPrecedence(operators.top()) >= getPrecedence(c)) {
                    postfix += operators.top();
                    cout << "操作符 " << c << " 优先级较低，出栈: " << operators.top() << endl;
                    operators.pop();
                }
                operators.push(c);
                cout << "操作符 " << c << " 入栈" << endl;
            }
        }
        
        while(!operators.empty()) {
            postfix += operators.top();
            cout << "最后出栈: " << operators.top() << endl;
            operators.pop();
        }
        
        cout << "后缀表达式: " << postfix << endl;
        return postfix;
    }
    
    // 计算后缀表达式
    int evaluatePostfix(const string& postfix) {
        cout << "\n=== 计算后缀表达式 ===" << endl;
        cout << "后缀表达式: " << postfix << endl;
        
        stack<int> operands;
        
        for(char c : postfix) {
            if(isDigit(c)) {
                operands.push(c - '0');
                cout << "数字 " << c << " 入栈" << endl;
            } else if(isOperator(c)) {
                if(operands.size() < 2) {
                    cout << "操作数不足" << endl;
                    return -1;
                }
                
                int b = operands.top(); operands.pop();
                int a = operands.top(); operands.pop();
                int result;
                
                switch(c) {
                    case '+': result = a + b; break;
                    case '-': result = a - b; break;
                    case '*': result = a * b; break;
                    case '/': result = a / b; break;
                }
                
                cout << "计算: " << a << " " << c << " " << b << " = " << result << endl;
                operands.push(result);
            }
        }
        
        if(operands.size() == 1) {
            cout << "最终结果: " << operands.top() << endl;
            return operands.top();
        } else {
            cout << "表达式格式错误" << endl;
            return -1;
        }
    }
};

// 4. 使用队列实现BFS（广度优先搜索）
class Graph {
private:
    int vertices;
    vector<vector<int>> adjList;

public:
    Graph(int v) : vertices(v) {
        adjList.resize(v);
    }
    
    void addEdge(int u, int v) {
        adjList[u].push_back(v);
        adjList[v].push_back(u); // 无向图
    }
    
    void bfs(int start) {
        cout << "\n=== BFS遍历 ===" << endl;
        cout << "从节点 " << start << " 开始BFS遍历" << endl;
        
        vector<bool> visited(vertices, false);
        queue<int> q;
        
        q.push(start);
        visited[start] = true;
        
        while(!q.empty()) {
            int current = q.front();
            q.pop();
            cout << "访问节点: " << current << endl;
            
            for(int neighbor : adjList[current]) {
                if(!visited[neighbor]) {
                    visited[neighbor] = true;
                    q.push(neighbor);
                    cout << "  发现未访问节点: " << neighbor << "，加入队列" << endl;
                }
            }
        }
    }
    
    void displayGraph() {
        cout << "图的邻接表表示:" << endl;
        for(int i = 0; i < vertices; i++) {
            cout << "节点 " << i << ": ";
            for(int neighbor : adjList[i]) {
                cout << neighbor << " ";
            }
            cout << endl;
        }
    }
};

// 5. 使用哈希表实现简单缓存
class SimpleCache {
private:
    int capacity;
    unordered_map<string, string> cache;
    queue<string> accessOrder;

public:
    SimpleCache(int cap) : capacity(cap) {
        cout << "创建简单缓存，容量: " << capacity << endl;
    }
    
    string get(const string& key) {
        if(cache.find(key) != cache.end()) {
            cout << "缓存命中: " << key << " = " << cache[key] << endl;
            return cache[key];
        } else {
            cout << "缓存未命中: " << key << endl;
            return "";
        }
    }
    
    void put(const string& key, const string& value) {
        if(cache.find(key) != cache.end()) {
            // 键已存在，更新值
            cache[key] = value;
            cout << "更新缓存: " << key << " = " << value << endl;
        } else {
            if(cache.size() >= capacity) {
                // 删除最旧的元素
                string oldestKey = accessOrder.front();
                accessOrder.pop();
                cache.erase(oldestKey);
                cout << "缓存已满，删除最旧元素: " << oldestKey << endl;
            }
            
            cache[key] = value;
            accessOrder.push(key);
            cout << "添加新元素: " << key << " = " << value << endl;
        }
    }
    
    void display() {
        cout << "当前缓存内容:" << endl;
        for(const auto& pair : cache) {
            cout << "  " << pair.first << " = " << pair.second << endl;
        }
    }
};

// 6. 综合应用：简单的计算器
class SimpleCalculator {
private:
    ExpressionEvaluator evaluator;

public:
    int calculate(const string& expression) {
        cout << "\n=== 简单计算器 ===" << endl;
        cout << "计算表达式: " << expression << endl;
        
        string postfix = evaluator.infixToPostfix(expression);
        int result = evaluator.evaluatePostfix(postfix);
        
        cout << "计算结果: " << result << endl;
        return result;
    }
};

int main() {
    cout << "=== 数据结构综合应用演示 ===" << endl;
    
    // 1. 括号匹配检查
    cout << "\n" << string(50, '=') << endl;
    isValidParentheses("()[]{}");
    cout << endl;
    isValidParentheses("([)]");
    cout << endl;
    isValidParentheses("((()))");
    
    // 2. LRU缓存
    cout << "\n" << string(50, '=') << endl;
    LRUCache lru(3);
    lru.put(1, 10);
    lru.put(2, 20);
    lru.put(3, 30);
    lru.display();
    
    lru.get(2);
    lru.display();
    
    lru.put(4, 40);
    lru.display();
    
    // 3. 表达式求值
    cout << "\n" << string(50, '=') << endl;
    ExpressionEvaluator evaluator;
    evaluator.infixToPostfix("3+4*2");
    evaluator.evaluatePostfix("342*+");
    
    // 4. 图遍历
    cout << "\n" << string(50, '=') << endl;
    Graph g(6);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(1, 4);
    g.addEdge(2, 5);
    
    g.displayGraph();
    g.bfs(0);
    
    // 5. 简单缓存
    cout << "\n" << string(50, '=') << endl;
    SimpleCache cache(3);
    cache.put("name", "Alice");
    cache.put("age", "25");
    cache.put("city", "Beijing");
    cache.display();
    
    cache.get("name");
    cache.put("country", "China");
    cache.display();
    
    // 6. 简单计算器
    cout << "\n" << string(50, '=') << endl;
    SimpleCalculator calc;
    calc.calculate("2+3*4");
    calc.calculate("(2+3)*4");
    
    cout << "\n=== 总结 ===" << endl;
    cout << "本演示展示了以下数据结构的综合应用:" << endl;
    cout << "1. 栈：括号匹配、表达式求值" << endl;
    cout << "2. 队列：BFS遍历、LRU缓存" << endl;
    cout << "3. 哈希表：LRU缓存、简单缓存" << endl;
    cout << "4. 链表：LRU缓存的实现" << endl;
    cout << "5. 图：BFS遍历" << endl;
    
    return 0;
}
